package day_2023_7_to_10;

/**
 * @author haomin
 * @date 2023/08/10 23:25
 **/
public class Day_8_10 {
    class Solution {
        public int fib(int n) {
            if(n <= 1) return n == 0 ? 0 : 1;
            int[] dp = new int[n+1];
            dp[0] = 0; dp[1] = 1;
            for(int i = 2; i <= n; ++i) {
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
            }
            return dp[n];
        }
    }
}